package org.xiaoxin.leetcode.array;

import java.util.Arrays;

/**
 * 11. 盛最多水的容器
 * <p>
 * 给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
 * <p>
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * <p>
 * 返回容器可以储存的最大水量。
 * <p>
 * 说明：你不能倾斜容器。
 * <p>
 * 示例 1：
 * 输入：height = [1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * <p>
 * 示例 2：
 * 输入：height = [1,1]
 * 输出：1
 * <p>
 * 提示：
 * n == height.length
 * 2 <= n <= 10^5
 * 0 <= height[i] <= 10^4
 * <p>
 * 难度：中等
 * 标签：数组、双指针、贪心
 *
 * @author xiaoxin
 */
public class _11_containerWithMostWater {

    /**
     * 方法一：双指针法（推荐）
     * 思路：使用双指针，从数组两端开始，每次移动较小高度的指针
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * <p>
     */
    public int maxArea(int[] height) {
        // 提示：
        // 1. 使用两个指针：left 指向数组开头，right 指向数组末尾
        // 2. 每次计算当前容器的面积：min(height[left], height[right]) * (right - left)
        // 3. 移动较小高度的指针，因为移动较大高度的指针不会得到更大的面积
        // 4. 持续追踪最大面积
        if (height == null || height.length == 0) {
            return 0;
        }
        int leftIndex = 0, rightIndex = height.length - 1;
        int maxArea = 0;
        while (leftIndex < rightIndex) {
            int area = Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex);
            maxArea = Math.max(area, maxArea);
            if (height[leftIndex] < height[rightIndex]) {
                leftIndex++;
            } else {
                rightIndex--;
            }
        }

        return maxArea;
    }

    /**
     * 方法二：暴力法（不推荐，仅供理解） -- 直接超时
     * 思路：尝试所有可能的两条线的组合，计算每种组合的面积
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * <p>
     */
    public int maxArea2(int[] height) {
        // 提示：
        // 1. 使用两层循环，外层循环i从0到n-2，内层循环j从i+1到n-1
        // 2. 计算每对(i,j)的面积：min(height[i], height[j]) * (j - i)
        // 3. 追踪最大面积
        int maxArea = 0;
        int n = height.length;
        for (int i = 0; i <= n - 2; i++) {
            for (int j = i + 1; j <= n - 1; j++) {
                int left = height[i];
                int right = height[j];
                int a = Math.min(left, right);
                int area = a * (j - i);
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }


    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 11. 盛最多水的容器 - 测试用例 ===\n");

        // 示例 1
        int[] height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        testCase("示例 1", height1, 49);

        // 示例 2
        int[] height2 = {1, 1};
        testCase("示例 2", height2, 1);

        // 额外测试用例

        // 测试用例 3：递增序列
        int[] height3 = {1, 2, 3, 4, 5};
        testCase("测试用例 3（递增序列）", height3, 6);

        // 测试用例 4：递减序列
        int[] height4 = {5, 4, 3, 2, 1};
        testCase("测试用例 4（递减序列）", height4, 6);

        // 测试用例 5：两端最高
        int[] height5 = {8, 1, 2, 3, 4, 5, 6, 7, 8};
        testCase("测试用例 5（两端最高）", height5, 64);

        // 测试用例 6：中间最高
        int[] height6 = {1, 2, 4, 3};
        testCase("测试用例 6（中间最高）", height6, 4);

        // 测试用例 7：相同高度
        int[] height7 = {3, 3, 3, 3, 3};
        testCase("测试用例 7（相同高度）", height7, 12);

        // 测试用例 8：只有两个元素
        int[] height8 = {2, 1};
        testCase("测试用例 8（只有两个元素）", height8, 1);

        // 测试用例 9：包含0
        int[] height9 = {0, 2, 0, 3, 1, 0, 1, 3, 2, 1};
        testCase("测试用例 9（包含0）", height9, 14);
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, int[] height, int expected) {
        System.out.println(testName + ":");
        System.out.println("输入数组: " + Arrays.toString(height));
        System.out.println("期望结果: " + expected);

        _11_containerWithMostWater solution = new _11_containerWithMostWater();

        // 测试方法一
        int[] height1 = height.clone();
        int result1 = solution.maxArea(height1);
        boolean method1Correct = result1 == expected;
        System.out.println("方法一结果: " + result1 + " " +
                (method1Correct ? "✅" : "❌"));

        // 测试方法二
        int[] height2 = height.clone();
        int result2 = solution.maxArea2(height2);
        boolean method2Correct = result2 == expected;
        System.out.println("方法二结果: " + result2 + " " +
                (method2Correct ? "✅" : "❌"));


        boolean allCorrect = method1Correct && method2Correct;
        System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        System.out.println();
    }
} 